from typing import List


# 根据最大矩形修改而来，只需计算矩形中包含的最大正方形即可！
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0: return 0
        n = len(matrix[0])
        if n == 0: return 0
        
        s_max = 0
        heights = [0] * n  # 上一层的累计高度
        for i in range(m):  # 对每一行进行单调栈计算
            heights = [0 if matrix[i][k] == '0' else heights[k]+1 for k in range(n)]
            heights = [0] + heights + [0]  # 哨兵
            stack = [0]  # 先把首部的哨兵下标加入
            for j in range(1, n+2):  # 一直到最后一个哨兵的下标
                while heights[j] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = j - stack[-1] - 1
                    s_max = max(s_max, h*h if h <= w else w*w)  # the only difference
                stack.append(j)
            heights = heights[1:-1]
        
        return s_max
